This invention relates generally to binary translation and compilation of source code for use in computer systems and more particularly to data flow analysis in translation and compiliation systems.
As it is known in the art, computer systems which generally include a central processing unit (CPU), a main memory, and an input-output device interconnected by a system bus are used to execute computer programs to perform a useful task. One type of computer program is an operating system which is used to interface the CPU to an application program. The aforementioned application program is used by a user of the computer system to perform the useful task.
The operating system includes the software resources needed by the computer system to interface hardware elements to the computer system as well as to interface the application program and other programs to the computer system.
Application programs typically include programs, such as word processors, which execute on the computer system under the control of the operating system. One technique commonly used to produce a binary image includes compiling source code written in a programming language to produce object code. The object code is typically linked with a linker to produce the binary image. Another technique is to convert a executable image of an application program for execution in a computer system of a first computer architecture into a executable for a different computer architecture. Generally, without some conversion binary images made for one particular architecture and operating system cannot execute on a different architecture and/or operating system.
A compiler generally includes a front end which converts the source code into an intermediate representation and a back end which for example optimizes the intermediate language representation to permit the production of efficient object code. Data flow analysis is typically performed as part of the optimizations. In a complier a routine is generally used as the basic unit upon which data flow analysis is performed.
Optimizers included in existing binary translators that perform data flow analysis typically perform such analysis using a basic block, rather than a routine. A basic block is generally defined as one or more intermediate language statements with no embeded control flow, e.g., no intervening entry or exit point. A routine generally comprises many basic blocks. An optimizer in binary translator generally uses the basic block as the unit of optimization processing due to the lack of program structure in the binary image.
Generally, data flow analysis examines a flow graph representation of a computer program determining the state of the computer program, for example, the value of a program variable, at different points in a optimizable unit of the program. The possible execution control flow paths that comprise the unit are examined and typically, information is gathered about what can be true at various points in paths of the flow graph. For example, the values of a program variable are determined for each different possible execution path in the computer program. If data flow analysis indicates that a program variable is never used or read in a computer program, that variable and its associated storage can typically be eliminated.
One problem encountered in performing data flow analysis in compilers is how to represent the results of the analysis in a manner which affords efficient use of computer system resources, such as an organization of the analysis information that minimizes storage requirements while the organization also affords efficient retrieval of the analysis information.
A problem also encountered in performing data flow analysis in binary translation, as with compilers as previously discussed, is how to represent the results of the analysis in a manner which affords efficient use of computer system resources.
Techniques currently used by compilers in storing and retrieving data flow analysis information generally have problems with efficiency and are not readily scalable to larger programs without introducing undesirable restrictions and drawbacks.
One common mechanism used to represent data flow analysis information in an optimizing compiler includes using a first technique for representing global data flow information and a second, different technique for representing local data flow information.
One way in which compilers typically represent global data flow analysis information is a "dense" representation, such as using bit vectors to represent summary results of data flow analysis. Generally, multiple bit vectors are associated with each basic block to represent global information about the basic block with respect to other basic blocks. A position in a bit vector is reserved for each data item. For example, a representation of the data flow analysis information associates two (2) bit vectors representing global data flow analysis information with each basic block. A first bit vector (GEN) has a bit corresponding to each data item that is known to at least one other basic block. A bit is set within GEN if the corresponding data item is defined within the basic block. A second bit vector (USE) also contains a bit corresponding to each data item known to at least one other basic block. A bit is set within USE if there is an upwardly exposed use of the corresponding data item within the basic block. That is, the bit is set if the data definition within the basic block depends on another data definition outside of the basic block.
This dense representation of data flow analysis information tends to be computationally inefficient when gathering information needed to perform optimizations and expensive in terms of execution time and storage. A large fixed amount of storage is required. In reference to the previous example of representing global information using two (2) bit vectors per basic block, if there are "N" data items and "M" basic blocks, the fixed storage cost for only global information is the product of ("N"* "M"*2). In computational complexity terms, the storage cost is of order O(n.sup.2). This technique is generally not scaleable since, as routines and programs become larger, the fixed amount of storage tends to increase as a power of two (2).
As an improvement to reduce the amount of fixed storage needed, some implementations have limited the data definitions that are tracked locally and/or globally. For example, an implementation performs global optimizations upon only certain types of variables. This decreases the amount of storage required, but, does not provide direct or unified connectivity with one information data structure. Additionally, this improvement adds the restriction of limiting the number and types of data definitions upon which optimizations can be performed.
Another drawback of the bit vector representation is that a bit vector is not an information "rich" data structure. Bit vectors typically represent derived or summary information about a basic block. Not much information can be recorded and retrieved from one bit of storage per data item. For example, in performing an optimization using the global data flow information, it is necessary to locate the precise instruction or statement within the basic block that is defining the data item. Bit vectors do not capture this detailed information. Therefore, another mechanism is needed to provide the more specific, detailed information usually required about global data flow.
Typically, one of two techniques is used to obtain the additional detailed information associated with global data flow analysis. One technique uses a subordinating data structure to represent the detailed information, for example, such as a pointer to the actual instruction that performs a data item definition and a data item reference. A second technique used is to locate the actual instruction(s) needed at a particular instance during optimization by performing a sequential search, for example, of instructions within a basic block.
In addition to the large amount of fixed storage typically needed in optimization processing using bit vectors, another drawback of the foregoing representation for global data flow information is the lack of direct connectivity between basic blocks for data items having significance that transcends a basic block, such as a data definition in a first basic block having a global reference in a second basic block. Direct connectivity affords efficient information retrieval. For example, given a global definition, when performing an optimization, the optimizer needs to locate all references or data dependencies on the data definition. A bit vector, like the USE vector previously described, is associated with each basic block. To determine all the needed references, the optimizer examines the USE bit vector of each basic block to locate which basic blocks have dependencies. However, when performing optimizations such as constant propagation, the optimizer also needs to know the actual statement or instruction as determined using one of the two techniques previously described for obtaining the additional detailed information associated with global data flow analysis.
Using either technique with the bit vector does not provide direct connectivity that includes, for example, direct connections from a definition in one basic block to all references in other basic blocks. Such direct connectivity is desired to have an efficient propagation and retrieval of information since these are typically the most frequent activities performed by an optimizer.
As previously mentioned, local data flow information is typically represented using a second technique different from the foregoing global data flow scheme. One common technique used to represent local data flow analysis information includes building a directed graph comprising nodes and directed arrows or edges connecting the nodes. In one implementation, a node is a first code cell connected to another second code cell by a directed edge represented as a structure with a pointer connecting the first and second codecells. The first code cell represents a data definition. The second code cell represents a reference to the data definition. Frequently, an implementation of the directed edge is doubly connected in that the second code cell is also connected to the first code cell allowing the directed edge to be traversed in both directions, e.g., source to destination and vice-versa.
This directed graph for storing local data flow information provides a degree of direct connectivity, e.g., given a local data definition, the optimizer can directly connect to all local references to the data definition. However, this does not provide direct connectivity to any remaining global references, for example.
A drawback arises from using two different techniques for each of local and global data flow information rather than use a single technique for both. The amount of computer resources, such as memory, to store the associated code for building data flow information is generally greater since a minimal amount of code is typically shared in an implementation of both the local and global data flow analysis. Having more code typically increases associated development costs, such as additional testing. Adding functionality usually includes implementing and debugging one routine for local data flow analysis and another different routine for global data flow analysis because they cannot share the same routine.